/*
 * contrib/hstore/hstore_gist.c
 */
#include "postgres.h"

#include "access/gist.h"
#include "access/reloptions.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "hstore.h"
#include "utils/pg_crc.h"

/* gist_hstore_ops 操作类选项 */
typedef struct
{
	int32		vl_len_;		/* varlena 头部（请勿直接触摸！） */
	int			siglen;			/* 签名长度（字节） */
} GistHstoreOptions;

/* bigint 定义 */
#define BITBYTE 8
#define SIGLEN_DEFAULT	(sizeof(int32) * 4)
#define SIGLEN_MAX		GISTMaxIndexKeySize
#define SIGLENBIT(siglen) ((siglen) * BITBYTE)
#define GET_SIGLEN()	(PG_HAS_OPCLASS_OPTIONS() ? \
						 ((GistHstoreOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
						 SIGLEN_DEFAULT)


typedef char *BITVECP;

#define LOOPBYTE(siglen) \
			for (fc_i = 0; fc_i < (siglen); fc_i++)

#define LOOPBIT(siglen) \
			for (fc_i = 0; fc_i < SIGLENBIT(siglen); fc_i++)

/* 注意对这些宏的参数进行多次求值！ */
#define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) )
#define GETBITBYTE(x,i) ( (*((char*)(x)) >> (i)) & 0x01 )
#define CLRBIT(x,i)   GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITBYTE ) )
#define SETBIT(x,i)   GETBYTE(x,i) |=  ( 0x01 << ( (i) % BITBYTE ) )
#define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITBYTE )) & 0x01 )
#define HASHVAL(val, siglen) (((unsigned int)(val)) % SIGLENBIT(siglen))
#define HASH(sign, val, siglen) SETBIT((sign), HASHVAL(val, siglen))

typedef struct
{
	int32		vl_len_;		/* varlena 头部（请勿直接触摸！） */
	int32		flag;
	char		data[FLEXIBLE_ARRAY_MEMBER];
} GISTTYPE;

#define ALLISTRUE		0x04

#define ISALLTRUE(x)	( ((GISTTYPE*)x)->flag & ALLISTRUE )

#define GTHDRSIZE		(VARHDRSZ + sizeof(int32))
#define CALCGTSIZE(flag, siglen) ( GTHDRSIZE+(((flag) & ALLISTRUE) ? 0 : (siglen)) )

#define GETSIGN(x)		( (BITVECP)( (char*)x+GTHDRSIZE ) )

#define SUMBIT(val) (		\
	GETBITBYTE((val),0) + \
	GETBITBYTE((val),1) + \
	GETBITBYTE((val),2) + \
	GETBITBYTE((val),3) + \
	GETBITBYTE((val),4) + \
	GETBITBYTE((val),5) + \
	GETBITBYTE((val),6) + \
	GETBITBYTE((val),7)   \
)

#define GETENTRY(vec,pos) ((GISTTYPE *) DatumGetPointer((vec)->vector[(pos)].key))

#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )

/* 计算单个数据块 CRC-32 的简写。 */
static pg_crc32
fc_crc32_sz(char *fc_buf, int fc_size)
{
	pg_crc32	fc_crc;

	INIT_TRADITIONAL_CRC32(fc_crc);
	COMP_TRADITIONAL_CRC32(fc_crc, fc_buf, fc_size);
	FIN_TRADITIONAL_CRC32(fc_crc);

	return fc_crc;
}


PG_FUNCTION_INFO_V1(ghstore_in);
PG_FUNCTION_INFO_V1(ghstore_out);


Datum ghstore_in(PG_FUNCTION_ARGS)
{
	elog(ERROR, "Not implemented");
	PG_RETURN_DATUM(0);
}

Datum ghstore_out(PG_FUNCTION_ARGS)
{
	elog(ERROR, "Not implemented");
	PG_RETURN_DATUM(0);
}

static GISTTYPE *
fc_ghstore_alloc(bool fc_allistrue, int fc_siglen, BITVECP fc_sign)
{
	int			fc_flag = fc_allistrue ? ALLISTRUE : 0;
	int			fc_size = CALCGTSIZE(fc_flag, fc_siglen);
	GISTTYPE   *fc_res = palloc(fc_size);

	SET_VARSIZE(fc_res, fc_size);
	fc_res->flag = fc_flag;

	if (!fc_allistrue)
	{
		if (fc_sign)
			memcpy(GETSIGN(fc_res), fc_sign, fc_siglen);
		else
			memset(GETSIGN(fc_res), 0, fc_siglen);
	}

	return fc_res;
}

PG_FUNCTION_INFO_V1(ghstore_consistent);
PG_FUNCTION_INFO_V1(ghstore_compress);
PG_FUNCTION_INFO_V1(ghstore_decompress);
PG_FUNCTION_INFO_V1(ghstore_penalty);
PG_FUNCTION_INFO_V1(ghstore_picksplit);
PG_FUNCTION_INFO_V1(ghstore_union);
PG_FUNCTION_INFO_V1(ghstore_same);
PG_FUNCTION_INFO_V1(ghstore_options);

Datum ghstore_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	int			fc_siglen = GET_SIGLEN();
	GISTENTRY  *fc_retval = fc_entry;

	if (fc_entry->leafkey)
	{
		GISTTYPE   *fc_res = fc_ghstore_alloc(false, fc_siglen, NULL);
		HStore	   *fc_val = DatumGetHStoreP(fc_entry->key);
		HEntry	   *fc_hsent = ARRPTR(fc_val);
		char	   *fc_ptr = STRPTR(fc_val);
		int			fc_count = HS_COUNT(fc_val);
		int			fc_i;

		for (fc_i = 0; fc_i < fc_count; ++fc_i)
		{
			int			fc_h;

			fc_h = fc_crc32_sz((char *) HSTORE_KEY(fc_hsent, fc_ptr, fc_i),
						 HSTORE_KEYLEN(fc_hsent, fc_i));
			HASH(GETSIGN(fc_res), fc_h, fc_siglen);
			if (!HSTORE_VALISNULL(fc_hsent, fc_i))
			{
				fc_h = fc_crc32_sz((char *) HSTORE_VAL(fc_hsent, fc_ptr, fc_i),
							 HSTORE_VALLEN(fc_hsent, fc_i));
				HASH(GETSIGN(fc_res), fc_h, fc_siglen);
			}
		}

		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_res),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset,
					  false);
	}
	else if (!ISALLTRUE(DatumGetPointer(fc_entry->key)))
	{
		int32		fc_i;
		GISTTYPE   *fc_res;
		BITVECP		fc_sign = GETSIGN(DatumGetPointer(fc_entry->key));

		LOOPBYTE(fc_siglen)
		{
			if ((fc_sign[fc_i] & 0xff) != 0xff)
				PG_RETURN_POINTER(fc_retval);
		}

		fc_res = fc_ghstore_alloc(true, fc_siglen, NULL);

		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_res),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset,
					  false);
	}

	PG_RETURN_POINTER(fc_retval);
}

/*
 * 因为类型 ghstore 不是可压缩的（并且不需要被压缩），
 * 这个函数可以是一个无操作。
 */
Datum ghstore_decompress(PG_FUNCTION_ARGS)
{
	PG_RETURN_POINTER(PG_GETARG_POINTER(0));
}

Datum ghstore_same(PG_FUNCTION_ARGS)
{
	GISTTYPE   *fc_a = (GISTTYPE *) PG_GETARG_POINTER(0);
	GISTTYPE   *fc_b = (GISTTYPE *) PG_GETARG_POINTER(1);
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);
	int			fc_siglen = GET_SIGLEN();


	if (ISALLTRUE(fc_a) && ISALLTRUE(fc_b))
		*fc_result = true;
	else if (ISALLTRUE(fc_a))
		*fc_result = false;
	else if (ISALLTRUE(fc_b))
		*fc_result = false;
	else
	{
		int32		fc_i;
		BITVECP		fc_sa = GETSIGN(fc_a),
					fc_sb = GETSIGN(fc_b);

		*fc_result = true;
		LOOPBYTE(fc_siglen)
		{
			if (fc_sa[fc_i] != fc_sb[fc_i])
			{
				*fc_result = false;
				break;
			}
		}
	}
	PG_RETURN_POINTER(fc_result);
}

static int32 fc_sizebitvec(BITVECP fc_sign, int fc_siglen)
{
	int32		fc_size = 0,
				fc_i;

	LOOPBYTE(fc_siglen)
	{
		fc_size += SUMBIT(fc_sign);
		fc_sign = (BITVECP) (((char *) fc_sign) + 1);
	}
	return fc_size;
}

static int fc_hemdistsign(BITVECP fc_a, BITVECP fc_b, int fc_siglen)
{
	int			fc_i,
				fc_dist = 0;

	LOOPBIT(fc_siglen)
	{
		if (GETBIT(fc_a, fc_i) != GETBIT(fc_b, fc_i))
			fc_dist++;
	}
	return fc_dist;
}

static int fc_hemdist(GISTTYPE *fc_a, GISTTYPE *fc_b, int fc_siglen)
{
	if (ISALLTRUE(fc_a))
	{
		if (ISALLTRUE(fc_b))
			return 0;
		else
			return SIGLENBIT(fc_siglen) - fc_sizebitvec(GETSIGN(fc_b), fc_siglen);
	}
	else if (ISALLTRUE(fc_b))
		return SIGLENBIT(fc_siglen) - fc_sizebitvec(GETSIGN(fc_a), fc_siglen);

	return fc_hemdistsign(GETSIGN(fc_a), GETSIGN(fc_b), fc_siglen);
}

static int32 fc_unionkey(BITVECP fc_sbase, GISTTYPE *fc_add, int fc_siglen)
{
	int32		fc_i;
	BITVECP		fc_sadd = GETSIGN(fc_add);

	if (ISALLTRUE(fc_add))
		return 1;
	LOOPBYTE(fc_siglen)
		fc_sbase[fc_i] |= fc_sadd[fc_i];
	return 0;
}

Datum ghstore_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	int32		fc_len = fc_entryvec->n;

	int		   *fc_size = (int *) PG_GETARG_POINTER(1);
	int			fc_siglen = GET_SIGLEN();
	int32		fc_i;
	GISTTYPE   *fc_result = fc_ghstore_alloc(false, fc_siglen, NULL);
	BITVECP		fc_base = GETSIGN(fc_result);

	for (fc_i = 0; fc_i < fc_len; fc_i++)
	{
		if (fc_unionkey(fc_base, GETENTRY(fc_entryvec, fc_i), fc_siglen))
		{
			fc_result->flag |= ALLISTRUE;
			SET_VARSIZE(fc_result, CALCGTSIZE(ALLISTRUE, fc_siglen));
			break;
		}
	}

	*fc_size = VARSIZE(fc_result);

	PG_RETURN_POINTER(fc_result);
}

Datum ghstore_penalty(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* 始终 ISSIGNKEY */
	GISTENTRY  *fc_newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
	float	   *fc_penalty = (float *) PG_GETARG_POINTER(2);
	int			fc_siglen = GET_SIGLEN();
	GISTTYPE   *fc_origval = (GISTTYPE *) DatumGetPointer(fc_origentry->key);
	GISTTYPE   *fc_newval = (GISTTYPE *) DatumGetPointer(fc_newentry->key);

	*fc_penalty = fc_hemdist(fc_origval, fc_newval, fc_siglen);
	PG_RETURN_POINTER(fc_penalty);
}


typedef struct
{
	OffsetNumber pos;
	int32		cost;
} SPLITCOST;

static int fc_comparecost(const void *fc_a, const void *fc_b)
{
	return ((const SPLITCOST *) fc_a)->cost - ((const SPLITCOST *) fc_b)->cost;
}


Datum ghstore_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	OffsetNumber fc_maxoff = fc_entryvec->n - 2;

	GIST_SPLITVEC *fc_v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	int			fc_siglen = GET_SIGLEN();
	OffsetNumber fc_k,
				fc_j;
	GISTTYPE   *fc_datum_l,
			   *fc_datum_r;
	BITVECP		fc_union_l,
				fc_union_r;
	int32		fc_size_alpha,
				fc_size_beta;
	int32		fc_size_waste,
				fc_waste = -1;
	int32		fc_nbytes;
	OffsetNumber fc_seed_1 = 0,
				fc_seed_2 = 0;
	OffsetNumber *fc_left,
			   *fc_right;
	BITVECP		fc_ptr;
	int			fc_i;
	SPLITCOST  *fc_costvector;
	GISTTYPE   *fc__k,
			   *fc__j;

	fc_nbytes = (fc_maxoff + 2) * sizeof(OffsetNumber);
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nbytes);

	for (fc_k = FirstOffsetNumber; fc_k < fc_maxoff; fc_k = OffsetNumberNext(fc_k))
	{
		fc__k = GETENTRY(fc_entryvec, fc_k);
		for (fc_j = OffsetNumberNext(fc_k); fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
		{
			fc_size_waste = fc_hemdist(fc__k, GETENTRY(fc_entryvec, fc_j), fc_siglen);
			if (fc_size_waste > fc_waste)
			{
				fc_waste = fc_size_waste;
				fc_seed_1 = fc_k;
				fc_seed_2 = fc_j;
			}
		}
	}

	fc_left = fc_v->spl_left;
	fc_v->spl_nleft = 0;
	fc_right = fc_v->spl_right;
	fc_v->spl_nright = 0;

	if (fc_seed_1 == 0 || fc_seed_2 == 0)
	{
		fc_seed_1 = 1;
		fc_seed_2 = 2;
	}

	/* 形成初始 .. */
	fc_datum_l = fc_ghstore_alloc(ISALLTRUE(GETENTRY(fc_entryvec, fc_seed_1)), fc_siglen,
							GETSIGN(GETENTRY(fc_entryvec, fc_seed_1)));
	fc_datum_r = fc_ghstore_alloc(ISALLTRUE(GETENTRY(fc_entryvec, fc_seed_2)), fc_siglen,
							GETSIGN(GETENTRY(fc_entryvec, fc_seed_2)));

	fc_maxoff = OffsetNumberNext(fc_maxoff);
	/* 在 ... 之前排序 */
	fc_costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * fc_maxoff);
	for (fc_j = FirstOffsetNumber; fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
	{
		fc_costvector[fc_j - 1].pos = fc_j;
		fc__j = GETENTRY(fc_entryvec, fc_j);
		fc_size_alpha = fc_hemdist(fc_datum_l, fc__j, fc_siglen);
		fc_size_beta = fc_hemdist(fc_datum_r, fc__j, fc_siglen);
		fc_costvector[fc_j - 1].cost = abs(fc_size_alpha - fc_size_beta);
	}
	qsort((void *) fc_costvector, fc_maxoff, sizeof(SPLITCOST), fc_comparecost);

	fc_union_l = GETSIGN(fc_datum_l);
	fc_union_r = GETSIGN(fc_datum_r);

	for (fc_k = 0; fc_k < fc_maxoff; fc_k++)
	{
		fc_j = fc_costvector[fc_k].pos;
		if (fc_j == fc_seed_1)
		{
			*fc_left++ = fc_j;
			fc_v->spl_nleft++;
			continue;
		}
		else if (fc_j == fc_seed_2)
		{
			*fc_right++ = fc_j;
			fc_v->spl_nright++;
			continue;
		}
		fc__j = GETENTRY(fc_entryvec, fc_j);
		fc_size_alpha = fc_hemdist(fc_datum_l, fc__j, fc_siglen);
		fc_size_beta = fc_hemdist(fc_datum_r, fc__j, fc_siglen);

		if (fc_size_alpha < fc_size_beta + WISH_F(fc_v->spl_nleft, fc_v->spl_nright, 0.0001))
		{
			if (ISALLTRUE(fc_datum_l) || ISALLTRUE(fc__j))
			{
				if (!ISALLTRUE(fc_datum_l))
					MemSet((void *) fc_union_l, 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = GETSIGN(fc__j);
				LOOPBYTE(fc_siglen)
					fc_union_l[fc_i] |= fc_ptr[fc_i];
			}
			*fc_left++ = fc_j;
			fc_v->spl_nleft++;
		}
		else
		{
			if (ISALLTRUE(fc_datum_r) || ISALLTRUE(fc__j))
			{
				if (!ISALLTRUE(fc_datum_r))
					MemSet((void *) fc_union_r, 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = GETSIGN(fc__j);
				LOOPBYTE(fc_siglen)
					fc_union_r[fc_i] |= fc_ptr[fc_i];
			}
			*fc_right++ = fc_j;
			fc_v->spl_nright++;
		}
	}

	*fc_right = *fc_left = FirstOffsetNumber;

	fc_v->spl_ldatum = PointerGetDatum(fc_datum_l);
	fc_v->spl_rdatum = PointerGetDatum(fc_datum_r);

	PG_RETURN_POINTER(fc_v);
}


Datum ghstore_consistent(PG_FUNCTION_ARGS)
{
	GISTTYPE   *fc_entry = (GISTTYPE *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	int			fc_siglen = GET_SIGLEN();
	bool		fc_res = true;
	BITVECP		fc_sign;

	/* 此函数处理的所有情况都是不准确的 */
	*fc_recheck = true;

	if (ISALLTRUE(fc_entry))
		PG_RETURN_BOOL(true);

	fc_sign = GETSIGN(fc_entry);

	if (fc_strategy == HStoreContainsStrategyNumber ||
		fc_strategy == HStoreOldContainsStrategyNumber)
	{
		HStore	   *fc_query = PG_GETARG_HSTORE_P(1);
		HEntry	   *fc_qe = ARRPTR(fc_query);
		char	   *fc_qv = STRPTR(fc_query);
		int			fc_count = HS_COUNT(fc_query);
		int			fc_i;

		for (fc_i = 0; fc_res && fc_i < fc_count; ++fc_i)
		{
			int			fc_crc = fc_crc32_sz((char *) HSTORE_KEY(fc_qe, fc_qv, fc_i),
									   HSTORE_KEYLEN(fc_qe, fc_i));

			if (GETBIT(fc_sign, HASHVAL(fc_crc, fc_siglen)))
			{
				if (!HSTORE_VALISNULL(fc_qe, fc_i))
				{
					fc_crc = fc_crc32_sz((char *) HSTORE_VAL(fc_qe, fc_qv, fc_i),
								   HSTORE_VALLEN(fc_qe, fc_i));
					if (!GETBIT(fc_sign, HASHVAL(fc_crc, fc_siglen)))
						fc_res = false;
				}
			}
			else
				fc_res = false;
		}
	}
	else if (fc_strategy == HStoreExistsStrategyNumber)
	{
		text	   *fc_query = PG_GETARG_TEXT_PP(1);
		int			fc_crc = fc_crc32_sz(VARDATA_ANY(fc_query), VARSIZE_ANY_EXHDR(fc_query));

		fc_res = (GETBIT(fc_sign, HASHVAL(fc_crc, fc_siglen))) ? true : false;
	}
	else if (fc_strategy == HStoreExistsAllStrategyNumber)
	{
		ArrayType  *fc_query = PG_GETARG_ARRAYTYPE_P(1);
		Datum	   *fc_key_datums;
		bool	   *fc_key_nulls;
		int			fc_key_count;
		int			fc_i;

		deconstruct_array(fc_query,
						  TEXTOID, -1, false, TYPALIGN_INT,
						  &fc_key_datums, &fc_key_nulls, &fc_key_count);

		for (fc_i = 0; fc_res && fc_i < fc_key_count; ++fc_i)
		{
			int			fc_crc;

			if (fc_key_nulls[fc_i])
				continue;
			fc_crc = fc_crc32_sz(VARDATA(fc_key_datums[fc_i]), VARSIZE(fc_key_datums[fc_i]) - VARHDRSZ);
			if (!(GETBIT(fc_sign, HASHVAL(fc_crc, fc_siglen))))
				fc_res = false;
		}
	}
	else if (fc_strategy == HStoreExistsAnyStrategyNumber)
	{
		ArrayType  *fc_query = PG_GETARG_ARRAYTYPE_P(1);
		Datum	   *fc_key_datums;
		bool	   *fc_key_nulls;
		int			fc_key_count;
		int			fc_i;

		deconstruct_array(fc_query,
						  TEXTOID, -1, false, TYPALIGN_INT,
						  &fc_key_datums, &fc_key_nulls, &fc_key_count);

		fc_res = false;

		for (fc_i = 0; !fc_res && fc_i < fc_key_count; ++fc_i)
		{
			int			fc_crc;

			if (fc_key_nulls[fc_i])
				continue;
			fc_crc = fc_crc32_sz(VARDATA(fc_key_datums[fc_i]), VARSIZE(fc_key_datums[fc_i]) - VARHDRSZ);
			if (GETBIT(fc_sign, HASHVAL(fc_crc, fc_siglen)))
				fc_res = true;
		}
	}
	else
		elog(ERROR, "Unsupported strategy number: %d", fc_strategy);

	PG_RETURN_BOOL(fc_res);
}

Datum ghstore_options(PG_FUNCTION_ARGS)
{
	local_relopts *fc_relopts = (local_relopts *) PG_GETARG_POINTER(0);

	init_local_reloptions(fc_relopts, sizeof(GistHstoreOptions));
	add_local_int_reloption(fc_relopts, "siglen",
							"signature length in bytes",
							SIGLEN_DEFAULT, 1, SIGLEN_MAX,
							offsetof(GistHstoreOptions, siglen));

	PG_RETURN_VOID();
}
